#include "bitonicSort.h"

void BitonicSort::sort(Array *a)
{
    this->a = a->getArray();
    this->sortImpl(0, a->getCnt(), true);
    this->a = NULL; // Reset the array
}

void BitonicSort::sortImpl(unsigned long ind, unsigned long cnt, bool asc)
{
    if (cnt <= 1)
        return;
    unsigned long half = cnt / 2;
    sortImpl(ind, half, !asc);
    sortImpl(ind + half, cnt - half, asc);
    this->merge(ind, cnt, asc);
}

void BitonicSort::merge(unsigned long ind, unsigned long cnt, bool asc)
{
    if (cnt <= 1)
        return;
    unsigned long half = getPowerOfTwo(cnt);
    this->compare(ind, half, cnt, asc);
    this->merge(ind, half, asc);
    this->merge(ind + half, cnt - half, asc);
}

void BitonicSort::compare(unsigned ind, unsigned long m, unsigned long cnt, bool asc)
{
    for (unsigned long i = ind; i < ind + cnt - m; i++)
    {
        if (asc == (a[i] > a[i + m]))
        {
            int tmp = a[i];
            a[i] = a[i + m];
            a[i + m] = tmp;
        }
    }
}

unsigned long BitonicSort::getPowerOfTwo(unsigned long n) const
{
    unsigned long r = 1;
    while (r < n)
        r = r << 1;
    return (r >> 1);
}
